package DoExercise.HSP_ZCY.A015_暴力递归;

import java.util.ArrayList;
import java.util.List;

/**
 * 题目要求：打印一个字符串的全部排列，包含重复和不重复两种情况
 * <p>
 * 需要连续
 * 从左到右的尝试方式
 */
public class Code03_打印一个字符串全部排列
{
    public static void main(String[] args)
    {
        String s = "abc";
        List<String> ans1 = permutation(s);//重复
        for (String str : ans1)
        {
            System.out.println(str);
        }
        System.out.println("=======");
        List<String> ans2 = permutationNoRepeat(s);//不重复
        for (String str : ans2)
        {
            System.out.println(str);
        }
    }
    
    public static ArrayList<String> permutation(String str)
    {
        ArrayList<String> res = new ArrayList<>();
        if (str == null || str.length() == 0)
        {
            return res;
        }
        char[] chs = str.toCharArray();
        process(chs, 0, res);
        return res;
    }
    
    public static void process(char[] str, int i, ArrayList<String> res)
    {
        if (i == str.length)
        {
            res.add(String.valueOf(str));
        }
        //i未到终止位置，从i向后的所有位置都可以来到i位置
        for (int j = i; j < str.length; j++)
        {
            swap(str, i, j);
            process(str, i + 1, res);
            swap(str, i, j);//恢复现场
        }
    }
    
    /**
     * 打印一个字符串的全部排列，要求不要出现重复的排列
     * 当然可以用Set去重，但是需要遍历所有的字符串排列情况
     * 可以采用分支限界方法：利用已有的记录，有记录的不再遍历
     *
     * @param str
     * @return
     */
    public static ArrayList<String> permutationNoRepeat(String str)
    {
        ArrayList<String> res = new ArrayList<>();
        if (str == null || str.length() == 0) return res;
        char[] chs = str.toCharArray();
        process2(chs, 0, res);
        return res;
    }
    
    public static void process2(char[] str, int i, ArrayList<String> res)
    {
        if (i == str.length)
        {
            res.add(String.valueOf(str));
        }
        boolean[] visit = new boolean[26];
        for (int j = i; j < str.length; j++)
        {
            if (!visit[str[j] - 'a'])//已经出现过就不在走
            {
                visit[str[j] - 'a'] = true;
                swap(str, i, j);
                process2(str, i + 1, res);
                swap(str, i, j);
            }
        }
    }
    
    public static void swap(char[] chs, int i, int j)
    {
        char tmp = chs[i];
        chs[i] = chs[j];
        chs[j] = tmp;
    }
}
